package com.company.algo.niuke;

/**子数组的最大累加和问题【做过又忘了】
 *  动态规划
 *     dp[i]: 包括下标i之前的最大连续子数组和
 *     dp[i] = max(dp[i-1]+arr[i],arr[i])
 *     分别对应arr[i]加入当前子数组的和以及从头(i)开始计算连续子数组和的情况
 *     dp[0] = arr[0]
 *     需要用res来记录遍历中的最大值
 */
public class MaxSubArray {
    public int maxsumofSubarray (int[] arr) {
        int res = arr[0];
        int[] dp = new int[arr.length];
        dp[0] = res;
        for (int i = 1; i < arr.length; i++) {
            dp[i] = Math.max(dp[i-1]+arr[i],arr[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
